
from collections import defaultdict
#包含子串的字符串
class minWindow:
    def __init__(self):
        pass

    def run(self,s,t):
        if len(s)< len(t) :
            return ''
        hs,ht = defaultdict(int),defaultdict(int)
        for e in t:
            ht[e] += 1
        res = ""
        left,cnt = 0,0
        for right in range(len(s)):
            hs[s[right]] += 1
            if hs[s[right]] <= ht[s[right]]:
                cnt += 1

            # 等于表示单个元素相同，小于表示t中可能有重复的相同元素比较
            if cnt == len(t):
                # print("res",res)
                while True:  # s缩小左边界
                    if  hs[s[left]] <= ht[s[left]]  :  # s缩小左边界
                        break
                    hs[s[left]] -= 1
                    left += 1
                if not res or len(res) >  right -left +1 :
                    res = s[left:right+1]
                hs[s[left]] -= 1
                cnt -= 1
                left += 1

        return res

class minWindow2:
    def __init__(self):
        pass

    def run(self,s,t):
        need = defaultdict(int)
        res = (0,float('inf'))
        i,cnt = 0,len(t)
        for e in t:
            need[e] += 1
        for j,e in enumerate(s):
            if need[e] > 0:
                cnt -= 1
            need[e] -= 1
            if cnt == 0:
                while True:
                    if need[s[i]] == 0:
                        break
                    need[s[i]] += 1
                    i+=1
                if j-i < res[1] - res[0]:
                    res = (i,j)
                cnt += 1
                need[s[i]] += 1
                i += 1

        return  '' if len(s) < res[1]  else s[res[0]:res[1]+1]






if __name__ == '__main__':
    S= minWindow2()
    res = S.run('DOABECODEBANC','ABC')
    print(res)
